#include <iostream>
#include <vector>
using namespace std;
/*
想象一下炸弹人游戏，在你面前有一个二维的网格来表示地图，网格中的格子分别被以下三种符号占据：

'W' 表示一堵墙
'E' 表示一个敌人
'0'（数字 0）表示一个空位


请你计算一个炸弹最多能炸多少敌人。

由于炸弹的威力不足以穿透墙体，炸弹只能炸到同一行和同一列没被墙体挡住的敌人。

注意：你只能把炸弹放在一个空的格子里

示例:

输入: [["0","E","0","0"],["E","0","W","E"],["0","E","0","0"]]
输出: 3 
解释: 对于如下网格

0 E 0 0 
E 0 W E 
0 E 0 0

假如在位置 (1,1) 放置炸弹的话，可以炸到 3 个敌人

换言之，炸弹无视距离，同行同列直到撞墙

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/bomb-enemy
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
*/
int maxKilledEnemies(vector<vector<char>> &grid)
{
    if ((int)grid.size() == 0)
        return 0;
    int ans = 0, pre, n = (int)grid.size(), m = (int)grid[0].size();
    vector<vector<int>> boom(n, vector<int>(m, 0));
    for (int i = 0; i < n; ++i)
    {
        pre = 0;
        for (int j = 0; j < m; ++j)
        { // 从左往右
            if (grid[i][j] == 'W')
                pre = 0;
            else if (grid[i][j] == 'E')
                pre += 1;
            boom[i][j] += pre;
        }

        pre = 0;
        for (int j = m - 1; j >= 0; --j)
        { // 从右往左
            if (grid[i][j] == 'W')
                pre = 0;
            else if (grid[i][j] == 'E')
                pre += 1;
            boom[i][j] += pre;
        }
    }
    for (int j = 0; j < m; ++j)
    {
        pre = 0;
        for (int i = 0; i < n; ++i)
        { // 从上到下
            if (grid[i][j] == 'W')
                pre = 0;
            else if (grid[i][j] == 'E')
                pre += 1;
            boom[i][j] += pre;
        }

        pre = 0;
        for (int i = n - 1; i >= 0; --i)
        { // 从下到上
            if (grid[i][j] == 'W')
                pre = 0;
            else if (grid[i][j] == 'E')
                pre += 1;
            boom[i][j] += pre;
        }
    }
    for (int i = 0; i < n; ++i)
    {
        for (int j = 0; j < m; ++j)
            if (grid[i][j] == '0')
            {
                ans = max(ans, boom[i][j]);
            }
    }
    return ans;
}